%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Definicin del tipo de documento.                                            %
% Posibles tipos de papel: a4paper, letterpaper, legalpapper                  %
% Posibles tamaos de letra: 10pt, 11pt, 12pt                                  %
% Posibles clases de documentos: article, report, book, slides                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[titlepage,12pt,a4paper]{article}

% Paquetes que amplian la capacidad de LATEX
\usepackage[latin1]{inputenc} % Paquete de codificacion. Si tienen problemas, se puede reemplazar 'utf8x' por 'latin1'.
\usepackage[spanish]{babel} % Paquete para definir el idioma usado.
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{verbatim} % Para escribir codigo fuente.
\usepackage{color} % Paquete para darle color a la sintaxis del codigo fuente.
\usepackage{listings}
\usepackage{graphicx}

\lstset{ %
  language=C,                % the language of the code
  basicstyle=\small\tt, % Letra monoespaciada, parecida a la de una maquina de escribir
  numbers=left,                   % where to put the line-numbers
   stepnumber=2,                   % the step between two line-numbers. If it's 1, each line 
                                  % will be numbered
  numbersep=4pt,                  % how far the line-numbers are from the code
  backgroundcolor=\color{white},      % choose the background color. You must add \usepackage{color}
  numberstyle=\tiny\color{red},
  showspaces=false,               % show spaces adding particular underscores
  showstringspaces=false,         % underline spaces within strings
  showtabs=false,                 % show tabs within strings adding particular underscores
  frame=leftline,                   % adds a frame around the code
  rulecolor=\color{black},        % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. commens (green here))
  tabsize=2,                      % sets default tabsize to 2 spaces
  captionpos=b,                   % sets the caption-position to bottom
  breaklines=true,                % sets automatic line breaking
  breakatwhitespace=true,        % sets if automatic breaks should only happen at whitespace
  keywordstyle=\color{blue},          % keyword style
  commentstyle=\color{green},       % comment style
  escapeinside={\%*}{*)},            % if you want to add LaTeX within your code
  morekeywords={*,...}               % if you want to add more keywords to the set
}

\title{66.20\\Organizaci\'on de computadoras\\Trabajo pr\'actico 1\\Conjunto de instrucciones MIPS}
\author{B\'arbara Aguila Cudicio - 92071\\Francisco Javier Marin - 92378}
\date{Primer cuatrimestre 2013}

\begin{document}

\maketitle

\section{Objetivo}

En este TP compararemos las diferencias de velocidades entre sorts.
Los sorts a comparar ser\'an los siguientes:
\begin{itemize}
	\item Bubblesort escrito en C
	\item Shellsort escrito en C
	\item Shellsort escrito en ASM MIPS 
\end{itemize}

Como nota de implementacion, para las secuencias de gaps del shellsort se uso la secuencia de Knuth:
\begin{math} (3^k - 1) / 2 \end{math}
  no mayor a \begin{math}\lceil N / 3 \rceil \end{math}
\begin{math} = 1, 4, 13, 40, 121, \ldots \end{math} .

Los ordenes de los respectivos algoritmos ser\'an entonces:
\begin{itemize}
	\item Bubblesort:	\subitem Mejor caso \begin{math}O(N) \end{math}
				\subitem Peor caso \begin{math}O(N^2) \end{math}
	\item Shellsort:	\subitem Mejor caso \begin{math}O(N log(N)) \end{math}
				\subitem Peor caso \begin{math}O(N^{3/2}) \end{math}
\end{itemize}

\section{Speedup}

Para cada sort compararemos las velocidades tomando los tiempos de ejecuci\'on y luego calculando el speedup.
Las formulas relacionadas al c\'alculo del speedup son las siguientes:

\textbf{\\Terminolog\'ia:}

\begin{math} Su : \end{math}Speedup total

\begin{math} Su_L : \end{math}Speedup local

\begin{math} T_0 : \end{math}Tiempo original

\begin{math} T_n :  \end{math}Tiempo nuevo

\begin{math} P_nn :  \end{math}Parte no mejorable

\begin{math} P_m :  \end{math}Parte mejorable

\newpage
\textbf{\\F\'ormulas:}

\begin{displaymath} Su = T_0/T_n \end{displaymath}
\begin{displaymath} T_0 = T_0 (P_nm + P_m) \end{displaymath}
\begin{displaymath} T_n = T_0 (P_nm + P_m/Su_L) \end{displaymath}

Lo que nos interesara ser\'a el  \begin{math} Su_L \end{math} ya que el tiempo de parseo e impresi\'on del archivo podrian ser significativos, pero lo que queremos comparar es la diferencia en velocidad de los m\'etodos.

\section{Tiempos de ejecucion}

\subsection{Tiempo de I/O}

Uno esperar\'ia que como los tiempos de lectura de archivos son electromec\'anicos, y suelen ser ordenes mayores a las operaciones de CPU, fueran la parte m\'as lenta del programa.
Las operaciones de impresi\'on por pantalla tambien suelen ser tambi\'en muy lentas.
Sin embargo este tiempo sera aproximadamente fijo, y podrá considerarse la parte no mejorable del programa.

\section{Funciones implementadas en assembly}

Procede a detallarse las funciones utilizadas con su firma estilo C, y sus diagramas de stack correspondientes.

\subsection{void shellsort2(char** words, int arraysize)}

\includegraphics[width=138mm,height=61mm]{stackshell.png}

\subsection{void insertionSortParcial(char** words, int arraysize, int inicio, int gap)}

\includegraphics[width=138mm,height=88mm]{stackinsl.png}

\subsection{int strcmp2(char* c1, char* c2)} 

\includegraphics[width=138mm,height=26mm]{stackstrcmp.png}

\section{Compilaci\'on y corrida de pruebas}

Todas las compilaci\'on y tests se realizaron en el emulador dado por la catedra. Todos los tests fueron corridos en la misma PC.
El programa se compil\'o utilizando el makefile adjunto. Los flags utilizados por el mismo son "-Wall -g -pedantic -std=c99". Se supone que al no especificar nivel de optimizaci\'on el compilador usar O0.

\subsection{Tiempos individuales}

\subsubsection{Bubblesort C}

\textbf{Alice.txt}

real 30m 19.145s

user 30m 6.997s

sys 0m 11.336s \newline

\textbf{Beowulf.txt}

real 43m 8.527s

user 42m 53.673s

sys 0m 13.656s  \newline

\textbf{Otros}

No se pudieron realizar las pruebas debido al largo tiempo que estas llevaban.

\subsubsection{Shellsort C}

\textbf{Alice.txt}

real 0m 6.000s

user 0m 5.824s

sys 0m 0.192s  \newline

\textbf{Beowulf.txt}

real 0m 24.918s

user 0m 8.976s

sys 0m15.941s \newline

\textbf{Cyclopedia:}

real 1m 16.613s

user 0m 31.066s

sys 0m 45.515s \newline

\textbf{Quijote}

real 9m 40.027s

user 2m 30.728s

sys 5m 10.239s

\subsubsection{Shellsort ASM}

\textbf{Alice.txt:}

real 0m 56.762s

user 0m 40.977s

sys 0m 3.410s \newline

\textbf{Beowulf.txt}

real 1m 56.512s

user 1m 41.805s

sys 0m 14.662s  \newline

\textbf{Cyclopedia.txt}

real 12m 8.238s

user 11m 27.388s

sys 0m 40.527s \newline

\textbf{Quijote}

real    111m 39.039s

user    103m 42.286s

sys    5m 37.901s

\subsection{Grafico de tiempos individuales sin syscalls}

\includegraphics[width=138mm,height=60mm]{Tiempo.png}

\subsection{Comparacion BubbleSort C vs Shellsort C}

Solamente tenemos dos puntos de comparaci\'on debido a lo increiblemente lento que fue el Bubblesort.
Y sin embargo eso basta para ver una diferencia de speedup enorme.

\includegraphics[width=138mm,height=60mm]{Su2.png}

\subsection{ Shellsort ASM vs Shellsort C}

Nuestro Shellsort performo mucho peor el que fue optimizado por el compilador. Pero al menos supero al bubblesort de C debido a la diferencia de orden.

\includegraphics[width=138mm,height=60mm]{Su1.png}

\section{An\'alisis de los resultados}

Esperabamos que el c\'odigo en assembler fuese m\'as eficiente, por estar escrito en un lenguaje de menor nivel que C. Sin embargo, los resultados obtenidos fueron diferentes. Llegamos a la conclusi\'on de que la causa tiene que ser las optimizaciones introducidas por el compilador, que genera un c\'odigo assembler m\'as eficiente que el nuestro. Por otro lado, para facilitar la programaci\'on, al respetar la ABI se hacen muchos accesos innecesarios a memoria.

Tambi\'en esperabamos que la diferencia entre el bubblesort y shellsort no fuera tan grande conociendo los \'ordenes de ambos algoritmos, pero resulto ser inmensa, suponemos que debido a la gran cantidad de elementos que logragron aumentar la brecha entre los ordenes.  Mientras m\'as tiempo se uso para operaciones de I/O se vio un speedup local m\'as chico, pues se compartio m\'as parte no mejorable del tiempo total por decirlo de alguna forma.

Tambi\'en esperabamos que los algoritmos gastaran la mayor parte de su tiempo en operacion de I/O y que el sorting fuera trivial. Al ver los resultados, las operaciones de I/O efectivamente gastaron mucho tiempo, pero para todos los sorts los tiempos de ejecuci\'on no fueron triviales. Puede verse en nuestro sort m\'as rapido, shellsort de C, que sus tiempos de ejecucion ordenando fueron comparables a los gastados por llamadas de systema. Los otros sorts superaron en un orden o m\'as a los tiempos de I/O. 

Lamentablemente debido a la lentitud de los algoritmos en el ambiente emulado, no pudimos correr la totalidad de las pruebas. Pero con los puntos que conseguimos las diferencias son bastante claras de todas formas.

\newpage

\section{C\'odigo fuente}

\subsection{main.c}

\lstinputlisting[language=C]{../src/main.c}

\newpage

\subsection{lista.h}

\lstinputlisting[language=C]{../src/lista.h}

\newpage

\subsection{lista.c}

\lstinputlisting[language=C]{../src/lista.c}

\newpage

\subsection{c\_sorts.h}

\lstinputlisting[language=C]{../src/c_sorts.h}

\newpage

\subsection{c\_sorts.c}

\lstinputlisting[language=C]{../src/c_sorts.c}

\newpage

\subsection{shellsort.h}

\lstinputlisting[language=C]{../src/shellsort.h}

\subsection{shellsort.S}

\lstinputlisting[language={[x86masm]Assembler}]{../src/shellsort.S}

\end{document}
